﻿using System;

public class Solution912
{
    public int[] SortArray(int[] nums)
    {


        Partion(nums, 0, nums.Length - 1);
        return nums;


    }
    void Partion2(int[] nums, int start, int end)
    {

        if(start>=end) return;
       

        int left = start;
        int right = end;
        int val = nums[left];
        while (left < right)
        {
            while (left < right&&nums[right] >= val)//找到是比他严格小的
            {

                right--;
            }
            nums[left] = nums[right];

            while (left < right && nums[left] <= val)
            {

                left++;
            }
            nums[right] = nums[left];
   
        }
        nums[left] = val;
        Console.WriteLine(val);
        Partion(nums, start, left - 1);
        Partion(nums, left + 1, end);
    }
    void Partion(int[] nums, int start, int end)//随机选择中间的数字
    {

        if (start >= end) return;


        int left = start;
        int right = end;
        Random random = new Random();
        int pivot = random.Next(left, right);
        int val = nums[pivot];
        
        Swap(nums, pivot,left);
        while (left < right)
        {
            while (left < right && nums[right] >= val)//找到是比他严格小的
            {

                right--;
            }
            nums[left] = nums[right];

            while (left < right && nums[left] <= val)
            {

                left++;
            }
            nums[right] = nums[left];

        }
        nums[left] = val;
        Console.WriteLine(val);
        Partion(nums, start, left - 1);
        Partion(nums, left + 1, end);
    }
    static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

class Program912
{



    static void Main912(string[] args)
    {
        //int[] nums = [5, 1, 1, 2, 0, 0];
        int[] nums =[110, 100, 0];
        Solution912 solution = new Solution912();
        int[] res = solution.SortArray(nums);
        for (int i = 0; i < nums.Length; i++)
        {

            Console.Write(res[i]+",");
        }

    }
}